In multiprocessor systems with symmetrical processors in which no processors are given priority according to a predetermined hierarchy but all of the processors have equal rights of access to common resources (and are therefore defined as symmetrical), the problem of arbitrating between concurrent requests for access to common resources constitutes a severe problem, particularly with technological developments which require the use of ever quicker arbitration mechanisms which can operate in very short time intervals of about ten ns.
The arbitration mechanisms in synchronous systems are very simple; in a time interval defined by a periodic clock signal, each of the various processors which wish to obtain access to common resources has to assert a signal requesting access to the common resources on a connection wire (one per processor) to an arbitration unit.
At the end of the time interval, the various requests for access are loaded in an input register of the arbitration unit which, in an immediately subsequent time interval, determines, on the basis of predetermined arbitration criteria, to which of the processors to grant access to the common resources, and asserts a consent or GRANT signal associated with the arbitration carried out.
At the end of the arbitration time interval, this signal is loaded in an output register and is sent to the processor to which access has been granted.
This processor must deassert its request for access at the correct time (or keep it asserted if access to the common resources is required again) to allow a new arbitration operation to start.
There are various arbitration criteria of which, however, only that known as "round-robin" or circular-priority arbitration satisfies the requirements of multiprocessors with symmetrical processors, since all of the requests for access are satisfied without exclusions and without preference and, on average, the processors are served equally.
Whereas the fixed-priority arbitration criterion assigns to each processor a predetermined invariable priority relative to the other processors, the "round robin" arbitration criterion assigns a predetermined cyclic order but not an invariable relative priority to the various processors during access to common resources.
This order may be compared to a conventional or initial priority which is assigned in order to carry out a first arbitration operation on the basis of the relative priority thus assigned.
The relative priority of the processors is not fixed, however; if each of N processors is initially assigned a relative priority rank K, where K is between 1 and N, the priorities K decreasing from N to 1, and, in the case of a first arbitration operation, a request for access of rank K which may be other than N is served, the next arbitration is carried out by the assignation to the various processors of an order of decreasing priority from K-1 to 1, followed in order by the processors N to K, in decreasing order of priority.
Similarly, in all of the subsequent arbitration operations, the highest priority is assigned to the processor K-1 which is next in order to the processor K served in the immediately preceding arbitration operation.
In other words, the processors are assigned a cyclic order and a circular-priority pointer or round-robin pointer RRP which progresses cyclically, according to the arbitration carried out previously, identifies, at any particular time, which processor should be considered to have greatest priority and consequently the relative priorities of the other processors.
This criterion of progression of the RRP pointer may be defined as "skipping" or jumping and, although preferable, is not the only one which can be used to satisfy a circular-priority arbitration criterion.
For example, pseudo-random and "conventional" round-robin progression criteria are also known and used.
With the pseudo-random progression criterion, the RRP pointer is rotated by one or more positions in the cyclic order for each period of a clock signal (or for each predetermined multiple of the period of a clock signal).
The conventional round-robin progression criterion differs from the previous one solely in that the RRP pointer is rotated by one or more positions in the cyclic order for each grant of access.
Whereas a fixed-priority arbitration unit is quite easy to implement and is particularly fast since it is formed by an arbitration network in which the logic chains are constituted, theoretically, by only two logic elements in cascade (or three if the masking logic circuits generally included in an arbitration unit as discussed below are considered) circular (round-robin) priority arbitration networks are particularly complex, require a large number of logic components, and are therefore expensive.
Moreover, they necessarily require the formation of logic chains with at least 6 logic elements in cascade (7 if the masking circuits are considered) and are also intrinsically slower because the output load of several logic elements is much greater than is the case with fixed-priority arbitration networks.
There is also a known circuit embodiment which is formed in practice by a plurality of fixed-priority arbitration networks the outputs of which are applied as inputs to multiplexers, which theoretically reduces the lengths of the logic chains to 4 elements in cascade (5 if the masking circuits are considered) but requires a larger overall number of logic elements and considerably increases the input load of the network.
In the embodiments of the prior art, for a given circuit technology and number of input signals to be arbitrated, a circular-priority arbitration network thus has a propagation time of more than twice the propagation time of a fixed-priority arbitration network and cannot be reconciled with the operation of modern microprocessors which operate at frequencies of the order of 100 MHz and, to avoid a decline in their performance, require arbitration operations to be executed in very short times of the order of about ten ns.